package com.sheepone.util.algorithm.analysis;

import com.sheepone.util.regex.NumberRegexUtil;

import java.util.*;

/**
 * @author Miss.杨
 * @description
 * @since 2024/2/25 - 21:33
 */
public class IntegerAnalysisUtil {

    public static boolean isAnyLessThanZero(int... arr) {
        for (int d : arr) {
            if (d < 0) {
                return true;
            }
        }
        return false;
    }

    /**
     * 获取 不小于 && 最接近 n 的2的次方数
     *
     * @param n 目标数
     * @return 不小于 && 最接近 n 的2的次方数
     */
    public static int upper2Pow(int n) {
        n -= 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return n + 1;
    }

    /**
     * 判断一个数 是否是2的次方数
     * 1. (val & -val) == val
     * 2. (val & (~val + 1) ) == val
     * 3. val & (val - 1) == 0 && val != 0
     *
     * @param val
     * @return
     */
    public static boolean isPowerOfTwo(int val) {
        return (val & -val) == val;
    }

    /**
     * 判断一个数是否是正整数
     *
     * @param val 待判断的数
     * @return 判断结果
     */
    public static boolean isPositiveInteger(String val) {
        return val.matches(NumberRegexUtil.IS_POSITIVE_INTEGER);
    }

    /**
     * 判断一个数是否是整数
     *
     * @param val 待判断的数
     * @return 判断结果
     */
    public static boolean isInteger(String val) {
        return val.matches(NumberRegexUtil.IS_INTEGER);
    }

    /**
     * 交换数组中的两个元素
     *
     * @param arr
     * @param i
     * @param j
     */
    public static void swapInArray(int[] arr, int i, int j) {
        if (i != j && i <= arr.length && j < arr.length) {
            arr[i] = arr[j] ^ arr[i];
            arr[j] = arr[j] ^ arr[i];
            arr[i] = arr[j] ^ arr[i];
        }
    }

    /**
     * 交换矩阵中的两个元素
     *
     * @param matrix
     * @param fr
     * @param fc
     * @param sr
     * @param sc
     */
    public static void swapInMatrix(int[][] matrix, int fr, int fc, int sr, int sc) {
        matrix[fr][fc] = matrix[fr][fc] ^ matrix[sr][sc];
        matrix[sr][sc] = matrix[fr][fc] ^ matrix[sr][sc];
        matrix[fr][fc] = matrix[fr][fc] ^ matrix[sr][sc];
    }

    /**
     * 求和
     *
     * @param nums
     * @return
     */
    public int sum(int[] nums) {
        // stream会耗费较多的时间
        // Arrays.stream(nums).sum();
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        return sum;
    }

    /**
     * 前k个高频元素
     *
     * @param data
     * @param k
     * @return
     * @time-complexity n
     */
    public static int[] topKFrequent(int[] data, int k) {
        int[] ans = null;
        int cnt = 0;
        // 使用字典，统计每个元素出现的次数，元素为键，元素出现的次数为值
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int num : data) {
            if (map.containsKey(num)) {
                map.put(num, map.get(num) + 1);
            } else {
                map.put(num, 1);
            }
        }
        if (map.size() < k) {
            ans = new int[map.size()];
            for (Integer i : map.keySet()) {
                ans[cnt++] = i;
            }
            return ans;
        }

        //桶排序
        //将频率作为数组下标，对于出现频率不同的数字集合，存入对应的数组下标
        List<Integer>[] lists = new List[data.length + 1];
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            Integer value = entry.getValue();
            if (lists[value] == null) {
                lists[value] = new ArrayList<>();
            }
            lists[value].add(entry.getKey());
        }
        ans = new int[k];
        // 倒序遍历数组获取出现顺序从大到小的排列
        for (int i = lists.length - 1; i >= 0 && cnt < k; i--) {
            if (lists[i] == null) {
                continue;
            }
            for (Integer integer : lists[i]) {
                ans[cnt++] = integer;
            }
        }
        return ans;
    }

    /**
     * 是否为单调序列
     *
     * @param arr
     * @return
     */
    public static boolean isMonotonic(int[] arr) {
        boolean isIncreasing = true;
        int length = arr.length;
        for (int i = 1; i < length && isIncreasing; i++) {
            isIncreasing &= (arr[i] >= arr[i - 1]);
        }
        boolean isDecreasing = true;
        for (int i = 1; i < length && isDecreasing; i++) {
            isDecreasing &= (arr[i] <= arr[i - 1]);
        }
        return isIncreasing || isDecreasing;
    }

    /**
     * 给你一个长度为 n 的整数数组，每次操作将会使 n - 1 个元素增加 1 。返回让数组所有元素相等的最小操作次数。
     *
     * @param nums
     * @return
     * @time-complexity O(n)
     * @space-complexity O(1)
     * @url <a href="https://leetcode.cn/problems/minimum-moves-to-equal-array-elements/description/?envType=study-plan-v2&envId=jd-2023-fall-sprint">...</a>
     */
    public int minMoves(int[] nums) {
        int minNum = Arrays.stream(nums).min().getAsInt();
        int res = 0;
        for (int num : nums) {
            res += num - minNum;
        }
        return res;
    }

    /**
     * 给你一个整数数组 nums ，请计算数组的 中心下标 。
     * 数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。
     * 如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。
     * 如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1 。
     *
     * @param nums
     * @return
     * @time-complexity O(n)
     * @space-complexity O(1)
     */
    public int pivotIndex(int[] nums) {
        int total = sum(nums);
        int sum = 0;
        for (int i = 0; i < nums.length; ++i) {
            if (2 * sum + nums[i] == total) {
                return i;
            }
            sum += nums[i];
        }
        return -1;
    }

    /**
     * 给定已经按 升序 排列、由不同整数组成的数组 arr，返回满足 arr[i] == i 的最小索引 i。如果不存在这样的 i，返回 -1。
     *
     * @param arr
     * @return
     * @time-complexity O(logn)
     * @space-complexity O(1)
     */
    public int fixedPoint(int[] arr) {
        int n = arr.length;
        int low = 0, high = n;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (arr[mid] >= mid) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        return low < n && arr[low] == low ? low : -1;
    }


    public static void main(String[] args) {
        // [6,4,14,6,8,13,9,7,10,6,12]
        System.out.println(new Solution().maxJumps(new int[]{6, 4, 14, 6, 8, 13, 9, 7, 10, 6, 12}, 2));
    }

    static class Solution {
        private int[] arr;
        private int d;
        private int max = 0;
        private int[] steps;

        public int maxJumps(int[] arr, int d) {
            this.arr = arr;
            this.d = d;
            this.steps = new int[arr.length];
            for (int i = 0; i < arr.length; i++) {
                maxJumps(i, 1);
            }
            return max;
        }

        public void maxJumps(int index, int step) {
            if (steps[index] > step) {
                return;
            }
            steps[index] = step;
            max = Math.max(max, step);
            for (int i = index - 1; i >= index - d; i--) {
                if (i < 0 || arr[index] <= arr[i]) {
                    break;
                }
                maxJumps(i, step + 1);
            }
            for (int i = index + 1; i <= index + d; i++) {
                if (i >= arr.length || arr[index] <= arr[i]) {
                    break;
                }
                maxJumps(i, step + 1);
            }
        }
    }
}
